/*-------------------------------------------------------------------------
 *
 * orclauses.c
 *	  从连接 OR 子句中提取限制 OR 子句的例程
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/optimizer/util/orclauses.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/optimizer.h"
#include "optimizer/orclauses.h"
#include "optimizer/restrictinfo.h"


static bool fc_is_safe_restriction_clause_for(RestrictInfo *fc_rinfo, RelOptInfo *fc_rel);
static Expr *fc_extract_or_clause(RestrictInfo *fc_or_rinfo, RelOptInfo *fc_rel);
static void fc_consider_new_or_clause(PlannerInfo *fc_root, RelOptInfo *fc_rel,
								   Expr *fc_orclause, RestrictInfo *fc_join_or_rinfo);



/*
 * extract_restriction_or_clauses
 *	  检查连接的 OR-of-AND 子句，以查看是否可以提取出任何有用的限制 OR
 *	  子句。如果可以，则将它们添加到查询中。
 *
 * 尽管连接子句必须引用多个关系，但 OR of ANDs 子句可能包含只
 * 引用一个关系的子子句，并且可以用于为该关系构建一个限制子句。
 * 例如考虑
 *		WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45));
 * 我们可以将其转换为
 *		WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45))
 *			AND (a.x = 42 OR a.x = 44)
 *			AND (b.y = 43 OR b.z = 45);
 * 这使得后面的子句可以在扫描 a 和 b 时应用，
 * 可能作为索引资格条件，此外还减少了到达连接的行数。
 * 从本质上讲，这是对 CNF（AND of ORs 格式）的一次部分转换。
 * 然而，它并不完整，因为我们没有展开原始的 OR --- 这样做
 * 通常会使资格表达式膨胀，而收益不大。
 *
 * 添加的资格条件在某种程度上与原始 OR 是冗余的，因此会导致
 * 当最后形成连接关系时，连接关系的大小被低估。
 * （这在完全转换为 CNF 时也是如此；问题不在于转换，
 * 而在于 clauselist_selectivity 无法识别冗余条件。）我们
 * 可以通过改变原始 OR 子句的缓存选择性来弥补这种冗余，
 * 抵消基关系的预估大小的（有效）减少，以便预估的连接关系
 * 大小保持不变。这是一个重大黑客：它依赖于选择条件的
 * 被缓存这一事实，以及相同的 RestrictInfo 节点将在每个
 * 可能在形成连接关系时使用的 joininfo 列表中出现。
 * 并且在大小估计是非线性的情况下（即外连接和 IN 连接）它
 * 不起作用。但是比什么都不做要好。
 *
 * 我们检查每个基关系以查看与其关联的连接子句
 * 是否包含可提取的限制条件。如果是，则将这些条件
 * 添加到该关系的 baserestrictinfo 中，并更新连接子句的
 * 缓存选择性。请注意，相同的连接子句将从参与其中的
 * 每个 baserel 的角度重新检查，因此其缓存选择性可能
 * 会多次更新。
 */
void extract_restriction_or_clauses(PlannerInfo *fc_root)
{
	Index		fc_rti;

	/* 检查每个基关系以寻找潜在的连接 OR 子句 */
	for (fc_rti = 1; fc_rti < fc_root->simple_rel_array_size; fc_rti++)
	{
		RelOptInfo *fc_rel = fc_root->simple_rel_array[fc_rti];
		ListCell   *fc_lc;

		/* 可能会有空位对应于非基础关系的RTE */
		if (fc_rel == NULL)
			continue;

		Assert(fc_rel->relid == fc_rti);	/* 对数组进行完整性检查 */

		/* 忽略被视为“其他关系”的RTE */
		if (fc_rel->reloptkind != RELOPT_BASEREL)
			continue;

		/*
		 * 查找潜在有趣的 OR 连接子句。我们可以使用任何
		 * 通过参数化路径机制认为可以安全移动到此关系的
		 * 连接子句，尽管我们将要做的事情并不完全是参数化路径。
		 *
		 * 然而，似乎最好忽略被标记为冗余的子句
		 * （通过设置 norm_selec > 1）。这可能不会发生在 OR 子句
		 * 上，但我们还是小心点好。
		 */
		foreach(fc_lc, fc_rel->joininfo)
		{
			RestrictInfo *fc_rinfo = (RestrictInfo *) lfirst(fc_lc);

			if (restriction_is_or_clause(fc_rinfo) &&
				join_clause_is_movable_to(fc_rinfo, fc_rel) &&
				fc_rinfo->norm_selec <= 1)
			{
				/* 仅尝试为此关系提取一条资格条件 */
				Expr	   *fc_orclause = fc_extract_or_clause(fc_rinfo, fc_rel);

				/*
				 * 如果成功，决定我们是否想使用此子句，
				 * 如果是，则将其插入到该关系的 restrictinfo 列表中。
				 */
				if (fc_orclause)
					fc_consider_new_or_clause(fc_root, fc_rel, fc_orclause, fc_rinfo);
			}
		}
	}
}

/*
 * 给定的原始（非 OR）RestrictInfo 是否安全移动到该关系？
 */
static bool fc_is_safe_restriction_clause_for(RestrictInfo *fc_rinfo, RelOptInfo *fc_rel)
{
	/*
	 * 我们想要提到 rel 的子句，并且仅仅提到 rel。因此，特别是伪常量子句可以快速被拒绝。然后检查子句的变量成员资格。
	 */
	if (fc_rinfo->pseudoconstant)
		return false;
	if (!bms_equal(fc_rinfo->clause_relids, fc_rel->relids))
		return false;

	/* 我们不想对任何易变函数进行额外评估 */
	if (contain_volatile_functions((Node *) fc_rinfo->clause))
		return false;

	return true;
}

/*
 * 尝试从给定的连接 OR 子句中提取仅提到 "rel" 的限制子句。
 *
 * 我们必须能够从 OR 的每个分支中提取出至少一个与这个 rel 相关的条件，否则我们就无法使用它。
 *
 * 返回与 rel 相关的 OR 子句（不是 RestrictInfo！），如果无法提取到 OR 子句则返回 NULL。
 */
static Expr * fc_extract_or_clause(RestrictInfo *fc_or_rinfo, RelOptInfo *fc_rel)
{
	List	   *fc_clauselist = NIL;
	ListCell   *fc_lc;

	/*
	 * 扫描输入的 OR 子句的每个分支。注意我们深入到
	 * or_rinfo->orclause 中，该结构下面嵌入了 RestrictInfo 节点，
	 * 在顶层 OR/AND 结构下方。这是有用的，因为我们可以使用那些节点中的信息使得 is_safe_restriction_clause_for() 的检查
	 * 更加便宜。然而，我们将从返回的树中剥离这些节点，
	 * 这意味着如果子句被接受为限制子句，则会构建新的节点。
	 * 这看起来可能是浪费 —— 难道我们不能重用现有的 RestrictInfos 吗？但那要求假设选择性和其他缓存的数据
	 * 在限制子句和连接子句之间以相同的方式进行计算，这似乎并不理想。
	 */
	Assert(is_orclause(fc_or_rinfo->orclause));
	foreach(fc_lc, ((BoolExpr *) fc_or_rinfo->orclause)->args)
	{
		Node	   *fc_orarg = (Node *) lfirst(fc_lc);
		List	   *fc_subclauses = NIL;
		Node	   *fc_subclause;

		/* OR 参数应该是 AND 或子 RestrictInfos */
		if (is_andclause(fc_orarg))
		{
			List	   *fc_andargs = ((BoolExpr *) fc_orarg)->args;
			ListCell   *fc_lc2;

			foreach(fc_lc2, fc_andargs)
			{
				RestrictInfo *fc_rinfo = lfirst_node(RestrictInfo, fc_lc2);

				if (restriction_is_or_clause(fc_rinfo))
				{
					/*
					 * 递归处理嵌套的 OR。注意我们 *必须* 在这里递归，
					 * 这不仅仅是过度紧张的优化：我们必须深入足够远以找到并剥离表达式中的所有
					 * RestrictInfos。
					 */
					Expr	   *fc_suborclause;

					fc_suborclause = fc_extract_or_clause(fc_rinfo, fc_rel);
					if (fc_suborclause)
						fc_subclauses = lappend(fc_subclauses, fc_suborclause);
				}
				else if (fc_is_safe_restriction_clause_for(fc_rinfo, fc_rel))
					fc_subclauses = lappend(fc_subclauses, fc_rinfo->clause);
			}
		}
		else
		{
			RestrictInfo *fc_rinfo = castNode(RestrictInfo, fc_orarg);

			Assert(!restriction_is_or_clause(fc_rinfo));
			if (fc_is_safe_restriction_clause_for(fc_rinfo, fc_rel))
				fc_subclauses = lappend(fc_subclauses, fc_rinfo->clause);
		}

		/*
		 * 如果这个分支没有提取到任何东西，我们就无法对这个 OR 子句做任何事情。
		 */
		if (fc_subclauses == NIL)
			return NULL;

		/*
		 * 好的，将子子句添加到结果 OR。如果我们找到了多个子句，
		 * 我们需要一个 AND 节点。但如果我们只找到了一个，且它本身是一个
		 * OR 节点，则将它的子子句添加到结果中；这是为了保持 AND/OR 的扁平性（即，不允许 OR 直接在 OR 之下）。
		 */
		fc_subclause = (Node *) make_ands_explicit(fc_subclauses);
		if (is_orclause(fc_subclause))
			fc_clauselist = list_concat(fc_clauselist,
									 ((BoolExpr *) fc_subclause)->args);
		else
			fc_clauselist = lappend(fc_clauselist, fc_subclause);
	}

	/*
	 * 如果我们从每个分支中得到了限制子句，将它们包装在一个 OR
	 * 节点中。（从理论上讲，OR 节点可能是不必要的，如果只有
	 * 一个分支 —— 但那样的话输入的 OR 节点也是多余的。）
	 */
	if (fc_clauselist != NIL)
		return make_orclause(fc_clauselist);
	return NULL;
}

/*
 * 考虑成功提取的限制 OR 子句是否实际值得使用。如果是，则将其添加到计划者的数据结构中，
 * 并调整原始连接子句 (join_or_rinfo) 以进行补偿。
 */
static void fc_consider_new_or_clause(PlannerInfo *fc_root, RelOptInfo *fc_rel,
					   Expr *fc_orclause, RestrictInfo *fc_join_or_rinfo)
{
	RestrictInfo *fc_or_rinfo;
	Selectivity fc_or_selec,
				fc_orig_selec;

	/*
	 * 从新的 OR 子句构建一个 RestrictInfo。我们可以假设它是有效的
	 * 作为基本限制子句。
	 */
	fc_or_rinfo = make_restrictinfo(fc_root,
								 fc_orclause,
								 true,
								 false,
								 false,
								 fc_join_or_rinfo->security_level,
								 NULL,
								 NULL,
								 NULL);

	/*
	 * 估算它的选择性。（我们本可以更早地做到这一点，但在 RestrictInfo 表示上进行这样做可以使结果被缓存，
	 * 以节省后续的工作。）
	 */
	fc_or_selec = clause_selectivity(fc_root, (Node *) fc_or_rinfo,
								  0, JOIN_INNER, NULL);

	/*
	 * 仅当子句能够拒绝基础关系行的有用比例时，才值得将其添加到查询中；否则，它只会导致重复计算
	 * （因为在形成连接时我们仍然需要检查原始 OR 子句）。略显随意，我们将选择性阈值设置为 0.9。
	 */
	if (fc_or_selec > 0.9)
		return;					/* 忘了它 */

	/*
	 * 好的，将其添加到 rel 的限制子句列表中。
	 */
	fc_rel->baserestrictinfo = lappend(fc_rel->baserestrictinfo, fc_or_rinfo);
	fc_rel->baserestrict_min_security = Min(fc_rel->baserestrict_min_security,
										 fc_or_rinfo->security_level);

	/*
	 * 调整原始连接 OR 子句的缓存选择性，以补偿所添加的（但是多余的）低级别条件的选择性。这
	 * 应该使得连接关系得到的行估计大约与没有所有这些操作时的估计相同。
	 *
	 * XXX 重大黑客警报：这依赖于选择性将保持缓存的假设。
	 *
	 * XXX 另一个重大黑客：我们仅调整 norm_selec，即缓存的
	 * JOIN_INNER 语义的选择性，尽管连接子句可能是外连接子句。这部分是因为我们无法
	 * 在这里轻松识别相关的 SpecialJoinInfo，部分原因是我们所做的线性假设将会失败。（如果它是一个
	 * 外连接子句，“rel”必须在可为空的一侧，否则我们就不会来到这里。因此，连接大小的计算将会在
	 * “rel”的大小上呈现出相当非线性的关系，因此即便我们能够正确计算其原始值，也不清楚应该如何调整
	 * outer_selec。）
	 */
	if (fc_or_selec > 0)
	{
		SpecialJoinInfo fc_sjinfo;

		/*
		 * 为 JOIN_INNER 语义构建一个 SpecialJoinInfo。（比较
		 * costsize.c 中的 approx_tuple_count()。）
		 */
		fc_sjinfo.type = T_SpecialJoinInfo;
		fc_sjinfo.min_lefthand = bms_difference(fc_join_or_rinfo->clause_relids,
											 fc_rel->relids);
		fc_sjinfo.min_righthand = fc_rel->relids;
		fc_sjinfo.syn_lefthand = fc_sjinfo.min_lefthand;
		fc_sjinfo.syn_righthand = fc_sjinfo.min_righthand;
		fc_sjinfo.jointype = JOIN_INNER;
		/* 我们不打算尝试使剩余字段有效 */
		fc_sjinfo.lhs_strict = false;
		fc_sjinfo.delay_upper_joins = false;
		fc_sjinfo.semi_can_btree = false;
		fc_sjinfo.semi_can_hash = false;
		fc_sjinfo.semi_operators = NIL;
		fc_sjinfo.semi_rhs_exprs = NIL;

		/* 计算内连接大小 */
		fc_orig_selec = clause_selectivity(fc_root, (Node *) fc_join_or_rinfo,
										0, JOIN_INNER, &fc_sjinfo);

		/* 并黑客缓存选择性以保持连接大小不变 */
		fc_join_or_rinfo->norm_selec = fc_orig_selec / fc_or_selec;
		/* 确保结果保持在合理范围内，特别是不要“冗余” */
		if (fc_join_or_rinfo->norm_selec > 1)
			fc_join_or_rinfo->norm_selec = 1;
		/* 如上所述，我们不触及 outer_selec */
	}
}
